Monitoring traffic in communication networks is required for various applications, such as network management and optimization. Other applications include detecting traffic anomalies caused, for example, by malicious attacks. Methods for traffic monitoring and analysis are known in the art.
For example, U.S. Pat. No. 8,627,472, whose disclosure is incorporated herein by reference, describes a method for determining a heavy distinct hitter (HDH) in a data stream that comprises a plurality of element-value (e,v) pairs, by a data traffic monitor. The method includes receiving the plurality of (e,v) pairs from the data stream by an HDH module in the data traffic monitor, the HDH module being in communication with a counter block comprising a plurality of hash functions and a respective pair of distinct counting primitives associated with each hash function. The method further comprises adding each of the plurality of (e,v) pairs to one of the distinct counting primitives of the respective pair of distinct counting primitives for each of the plurality of hash functions in the counter block.
U.S. Pat. No. 8,406,132, whose disclosure is incorporated herein by reference, describes a method for monitoring a network. The method includes receiving, from each host of a set of two or more hosts of the network, a corresponding vector of M components constructed based on data packets received at the host during a time period, M being an integer greater than 1, and estimating a cardinality distribution for the hosts in the set, based on the constructed vectors and using an expectation-maximization algorithm. Constructing the vector includes updating a component of the vector of the corresponding host in response to the corresponding host receiving a data packet, the updating including selecting the component for updating by hashing one or more fields of the data packet received by the corresponding host.
Traffic monitoring sometimes involves counting a number of distinct values in a large set of elements. Methods for estimating the number of distinct values in a set are described, for example, by Flajole et al., in “HyperLog Log: the analysis of a near-optimal cardinality estimation algorithm,” the 2007 Conference on Analysis of Algorithms (AofA'07), Juan des Pins, France, Jun. 17-22, 2007, which is incorporated herein by reference.